package maxmiumScore;

import java.util.*;

public class Solution {
    public int maxmiumScore(int[] cards, int cnt) {
        // 取偶数个奇数 枚举k
        // k个奇数 + (cnt-k)个偶数
        // 分成k个奇数和cnt-k个偶数
        int ans = 0;
        List<Integer> odd = new ArrayList<>();
        List<Integer> even = new ArrayList<>();
        for (int i = 0; i < cards.length; i++) {
            if(cards[i]%2==0) {
                even.add(cards[i]);
            }else {
                odd.add(cards[i]);
            }
        }
        int[] oddPrev = new int[odd.size()+1];
        int[] evenPrev = new int[even.size()+1];
        odd.sort((o1, o2) -> o2-o1);
        even.sort((o1, o2) -> o2-o1);
        for (int i = 0; i < odd.size(); i++) {
            oddPrev[i+1] = oddPrev[i] + odd.get(i);
        }
        for (int i = 0; i < even.size(); i++) {
            evenPrev[i+1] = evenPrev[i]+even.get(i);
        }
        for (int k = 0; k <= cnt; k+=2) {
            if( k<=odd.size()&&(cnt-k)<=even.size() ) {
                ans = Math.max(oddPrev[k]+evenPrev[cnt-k],ans);
            }
        }
        return ans;
    }
}